﻿#include<iostream>
#include<map>
#include<vector>
#include<queue>
using namespace std;


//并查集
class Unionfindset {
public:
	Unionfindset(size_t n)
		: _ufs(n, -1)
	{
	}

	int Findroot(int x) {//找老大，返回老大的编号
		if (_ufs[x] < 0) return x;//没有老大说明自己就是老大
		else  return _ufs[x] = Findroot(_ufs[x]);//直接让下属连接老大，提高找老大的效率
	}

	void Union(int a, int b) {//交友、联合，将a看作上司
		int ar = Findroot(a);
		int br = Findroot(b);
		if (ar != br) {
			_ufs[ar] += _ufs[br];//算人数
			_ufs[br] = ar;//认老大
		}
	}

	size_t Setsize(int x) {//返回x所在团体的大小
		return -_ufs[Findroot(x)];
	}

	size_t count() {//返回团体个数
		size_t ans = 0;
		for (auto e : _ufs) {
			if (e < 0) ans++;
		}
		return ans;
	}
private:
	vector<int> _ufs;
};


//用邻接表实现的图
namespace Link_Table {
	template<class W>
	struct Edge {

		W _w;//权值
		int _src;//该边出发的顶点的值
		int _dst;//该边指向的顶点的值
		Edge<W>* _next;

		Edge(W w)
			:_dst(-1),
			_src(-1),
			_w(w),
			_next(nullptr)
		{
		}

		bool operator>(const Edge& b) const
		{//用于堆中的比较
			return _w > b._w;
		}

	};


	template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>//顶点类型，权值类型，无穷大，是否为有向图
	class Graph {
		typedef Edge<W> Edge;
		typedef Graph<V, W, MAX_W, Direction> Self;
	public:

		Graph() = default;

		Graph(const V* vertexs, size_t n) {//先存顶点，边后面再加上
			_vertexs = vector<V>(n, V());

			for (int i = 0; i < n; i++) {
				_vertexs[i] = vertexs[i];
				_vIndexMap[vertexs[i]] = i;
			}

			_LinkTable.resize(n, nullptr);
		}

		int GetVertexIndex(const V& v) {//返回顶点对应下标
			auto it = _vIndexMap.find(v);
			if (it != _vIndexMap.end()) {
				return it->second;
			}
			else {
				cout << "该顶点不存在" << endl;
				return -1;
			}
		}


		void _AddEdge(size_t sr, size_t ds, const W& w) {//用顶点下标添加边
			if (sr >= _vertexs.size() || ds >= _vertexs.size() || _LinkTable[sr] && _LinkTable[sr]->_dst == ds)//顶点不存在或者边已经有了
				return;

			Edge* temp = new Edge(w);
			temp->_src = sr;
			temp->_dst = ds;
			//头插，也只能头插
			temp->_next = _LinkTable[sr];
			_LinkTable[sr] = temp;

			if (!Direction) {//无向图要再加一条反过来的
				_AddEdge(ds, sr, w);
			}
		}

		void AddEdge(const V& v1, const V& v2, const W& w) {//用顶点添加边
			int sr = GetVertexIndex(v1);
			int ds = GetVertexIndex(v2);
			if (sr == -1 || ds == -1) return;
			_AddEdge(sr, ds, w);
		}


		void BFS() {
			if (_vertexs.size() == 0) return;

			queue<int> que;
			vector<bool> hash(_vertexs.size(), false);//是否被访问过
			int count = 0;//遍历过的顶点数

			while (count != _vertexs.size()) {
				for (int i = 0; i < hash.size(); i++) {//找一个没遍历过的入队
					if (!hash[i]) {
						que.push(i);
						hash[i] = true;
						count++;
						break;
					}
				}

				while (!que.empty()) {
					cout << _vertexs[que.front()] << ' ';

					Edge* cur = _LinkTable[que.front()];
					while (cur) {
						hash[cur->_dst] = true;
						count++;
						que.push(cur->dst);
						cur = cur->_next;
					}
					que.pop();
				}
				cout << endl;
			}
		}


		void _DFS_Func(vector<bool>& hash, int set) {//DFS核心递归函数
			if (hash[set]) return;

			cout << _vertexs[set] << ' ';//遍历当前顶点
			hash[set] = true;

			Edge* cur = _LinkTable[set];//寻找下一个顶点
			while (cur) {
				_DFS_Func(hash, cur->_dst);
				cur = cur->_next;
			}

		}

		void DFS() {//封装
			vector<bool> hash(_vertexs.size(), false);//是否被访问过
			while (1) {
				int i;
				for (i = 0; i < hash.size(); i++) {//检查遍历完了没
					if (!hash[i]) break;
				}

				if (i != hash.size())
					_DFS_Func(hash, i);//开始递归
				else break;

				cout << endl;
			}
		}


		W Kruskal(Self& mintree) {//返回权值总和，mintree用于存储最小生成树
			if (Direction) {
				cout << "该图为有向图" << endl;
				return W();
			}
			mintree._vertexs = _vertexs;//顶点都一样，边后面加
			//由于没有调用构造函数，邻接表要手动初始化
			mintree._LinkTable.resize(_vertexs.size(), nullptr);
			priority_queue<Edge, vector<Edge>, greater<Edge> > edgeque;//小根堆存储所有边
			for (int i = 0; i < _LinkTable.size(); i++) {
				Edge* cur = _LinkTable[i];
				while (cur) {
					edgeque.push(*cur);
					cur = cur->_next;
				}
			}
			Unionfindset ufs(_vertexs.size());//并查集
			int count = 1;//用于判断是不是生成树
			W sum = W();//计算权值之和
			while (count != _vertexs.size() && !edgeque.empty()) {
				Edge temp = edgeque.top();
				edgeque.pop();
				if (ufs.Findroot(temp._src) != ufs.Findroot(temp._dst)) {//用并查集判断是否构成环
					ufs.Union(temp._src, temp._dst);
					mintree._AddEdge(temp._src, temp._dst, temp._w);
					sum += temp._w;
					count++;
				}
			}
			if (count == _vertexs.size()) return sum;//判断是不是生成树
			else return W();
		}


		W Prim(Self& mintree, V src) {//src是起点
			if (Direction) {
				cout << "该图为有向图" << endl;
				return W();
			}
			mintree._vertexs = _vertexs;//顶点都一样，边后面加
			//由于没有调用构造函数，邻接表要手动初始化
			mintree._LinkTable.resize(_vertexs.size(), nullptr);
			size_t st = _vIndexMap[src];
			vector<bool> hash(_vertexs.size(), true);//记录未连接的顶点
			hash[st] = false;
			priority_queue<Edge, vector<Edge>, greater<Edge> > edgeque;//小根堆存储附近的所有边
			Edge* cur = _LinkTable[st];
			while (cur) {
				edgeque.push(*cur);
				cur = cur->_next;
			}

			int count = 1;
			W sum = W();
			while (count != _vertexs.size() && !edgeque.empty()) {
				Edge temp = edgeque.top();
				edgeque.pop();
				if (hash[temp._dst]) {
					hash[temp._dst] = false;
					mintree._AddEdge(temp._src, temp._dst, temp._w);
					count++;
					sum += temp._w;
					Edge* cur = _LinkTable[temp._dst];
					while (cur) {
						if (hash[cur->_dst]) edgeque.push(*cur);

						cur = cur->_next;
					}
				}
			}
			if (count == _vertexs.size()) return sum;//判断是不是生成树
			else return W();
		}


		//包含从起点出发到所有顶点的最短路径的信息
		void Dijkstra(V srci, vector<W>& path, vector<int>& parent) {
			size_t N = _vertexs.size();
			int sr = _vIndexMap[srci];
			path.resize(N, MAX_W);//到各个顶点的最短路径的长度
			parent.resize(N, -1);//各个顶点的在各自最短路径中的上一个节点，下面简称父节点，不断回溯即可确定其最短路径，值为-1表示父节点是自己
			vector<bool> hash(N, false);//true表示该顶点属于找到最短路径的S，反之则属于未处理的Q
			priority_queue<Edge, vector<Edge>, greater<Edge> > edgeque;//小根堆存储附近的所有边
			path[sr] = W();
			Edge t(0);
			t._dst = sr;
			t._src = sr;
			edgeque.push(t);
			while (!edgeque.empty()) {
				int cur = edgeque.top()._dst;//取的是顶点而不是边
				//判断一下从这条边到达是不是最短路径，是的话要更新路径长度和父节点
				if (path[edgeque.top()._src] + edgeque.top()._w <= path[edgeque.top()._dst]) {
					path[edgeque.top()._dst] = path[edgeque.top()._src] + edgeque.top()._w;
					parent[edgeque.top()._dst] = edgeque.top()._src;
				}
				edgeque.pop();
				if (hash[cur]) continue;
				hash[cur] = true;
				Edge* ep = _LinkTable[cur];//附近的边加入堆中
				while (ep) {
					if (!hash[ep->_dst]) {
						edgeque.push(*ep);
						if (path[cur] + ep->_w < path[ep->_dst]) {//松弛，父节点会在取出边时更新
							path[ep->_dst] = path[cur] + ep->_w;
						}
					}
					ep = ep->_next;
				}

			}
		}

		bool BellmanFord(V srci, vector<W>& path, vector<int>& parent) {
			size_t N = _vertexs.size();
			int sr = _vIndexMap[srci];
			path.resize(N, MAX_W);//到各个顶点的最短路径的长度
			parent.resize(N, -1);//各个顶点的在各自最短路径中的上一个节点，下面简称父节点，不断回溯即可确定其最短路径，值为-1表示父节点是自己
			vector<int> count(N, 0);//记录每个顶点遍历次数，防止负权环带来的死循环
			queue<int> verque;//顶点队列
			vector<bool>hash(N, false);//记录顶点是否在队列里，防重复

			path[sr] = 0;
			verque.push(sr);
			hash[sr] = true;
			while (!verque.empty()) {
				int temp = verque.front();
				verque.pop();
				hash[temp] = false;
				count[temp]++;
				if (count[temp] == N) return false;

				Edge* cur = _LinkTable[temp];
				while (cur) {
					if (path[cur->_dst] > cur->_w + path[cur->_src]) {//松弛
						path[cur->_dst] = cur->_w + path[cur->_src];
						parent[cur->_dst] = cur->_src;
						if (!hash[cur->_dst]) {
							verque.push(cur->_dst);
							hash[cur->_dst] = true;
						}
					}
					cur = cur->_next;
				}
			}
			return true;
		}



		void FloydWarShall(vector<vector<W>>& path, vector<vector<int>>& parent) {//path就是D
			size_t N = _vertexs.size();
			path.resize(N, vector<W>(N, MAX_W));//初始化
			parent.resize(N, vector<int>(N, -1));
			for (int i = 0; i < N; i++) {
				Edge* cur = _LinkTable[i];
				while (cur) {
					path[cur->_src][cur->_dst] = cur->_w;
					parent[cur->_src][cur->_dst] = cur->_src;//父节点也要初始化
					cur = cur->_next;
				}
				path[i][i] = W();
			}

			for (int k = 0; k < N; k++) {
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						if (path[i][k] != MAX_W && path[k][j] != MAX_W && i != j && path[i][j] > path[i][k] + path[k][j]) {//有经过顶点k
							path[i][j] = path[i][k] + path[k][j];
							parent[i][j] = parent[k][j];
						}
					}
				}
			}
		}
	

		void Print() {//输出图的内容
			for (auto i : _vertexs) {//打印顶点与下标关系
				cout << i << ' ';
			}
			cout << endl;
			for (int i = 0; i < _vertexs.size(); i++) cout << i << ' ';
			cout << endl << endl;

			for (int i = 0; i < _LinkTable.size(); i++) {//打印邻接表
				if (_LinkTable[i]) {
					cout << _vertexs[i] << '(' << i << "): ";
					Edge* cur = _LinkTable[i];
					while (cur) {
						cout <<_vertexs[cur->_dst]<< '(' << cur->_dst << ") --"<<cur->_w<<"--> ";
						cur = cur->_next;
					}
					cout << " nullptr" << endl;
				}
				else cout << _vertexs[i] << '(' << i << "): nullptr"<<endl;
			}
		}

		void PrinrtShotPath(V srci, vector<W>& dist, vector<int>& parent) {//打印以srci为起点的所有最短路径
			int sr = _vIndexMap[srci];
			for(int i=0;i<parent.size();i++)
			{
				if (i == sr) continue;
				vector<int> path;
				int cur = i;
				while (cur != -1) {
					path.push_back(cur);
					cur = parent[cur];
				}
				cout << "最短路径:" << endl;
				for (int i = path.size() - 1; i >= 0; i--) {
					cout << _vertexs[path[i]] << "->";
				}
				cout << endl;
				cout << "长度：" << dist[i] << endl<<endl;
			}
		}

	private:
		vector<V> _vertexs;//顶点
		map<V, int> _vIndexMap;//映射：顶点->编号
		vector<Edge*> _LinkTable;//邻接表（出边表）
	};
}



//用邻接矩阵实现的图
namespace Matrix {
	template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>//顶点类型，权值类型，无穷大，是否为有向图
	class Graph {
		typedef Graph<V, W, MAX_W, Direction> Self;
	public:

		Graph() = default;

		Graph(const V* vertexs, size_t n) {//先存顶点，边后面再加上
			_vertexs = vector<V>(n, V());

			for (int i = 0; i < n; i++) {
				_vertexs[i] = vertexs[i];
				_vIndexMap[vertexs[i]] = i;
			}
			_matrix = vector<vector<W> >(n, vector<W>(n, MAX_W));
			for (int i = 0; i < n; i++) {
				_matrix[i][i] = 0;
			}
		}

		int GetVertexIndex(const V& v) {//返回顶点对应下标
			auto it = _vIndexMap.find(v);
			if (it != _vIndexMap.end()) {
				return it->second;
			}
			else {
				cout << "该顶点不存在" << endl;
				return -1;
			}
		}
		void _AddEdge(size_t srci, size_t dsti, const W& w) {//用顶点下标添加边
			_matrix[srci][dsti] = w;
			if (!Direction) _matrix[dsti][srci] = w;
		}

		void AddEdge(const V& v1, const V& v2, const W& w) {//用顶点添加
			int sr = GetVertexIndex(v1);
			int ds = GetVertexIndex(v2);
			if (sr == -1 || ds == -1) return;
			_AddEdge(sr, ds, w);
		}

		void BFS() {
			if (_vertexs.size() == 0) return;

			queue<int> que;
			vector<bool> hash(_vertexs.size(), false);//是否被访问过
			int count = 0;//遍历过的顶点数

			while (count != _vertexs.size()) {
				for (int i = 0; i < hash.size(); i++) {//找一个没遍历过的入队
					if (!hash[i]) {
						que.push(i);
						hash[i] = true;
						count++;
						break;
					}
				}

				while (!que.empty()) {
					cout << _vertexs[que.front()] << ' ';

					for (int j = 0; j < _matrix.size(); j++) {
						if (_matrix[que.front()][j] != MAX_W && !hash[j]) {
							hash[j] = true;
							que.push(j);
							count++;
						}
					}
					que.pop();

				}
				cout << endl;
			}
		}

		void _DFS_Func(vector<bool>& hash, int set) {//DFS核心递归函数
			if (hash[set]) return;

			cout << _vertexs[set] << ' ';
			hash[set] = true;

			for (int j = 0; j < _matrix.size(); j++) {
				if (_matrix[set][j] != MAX_W) _DFS_Func(hash,j);
			}
		}

		void DFS() {//封装
			vector<bool> hash(_vertexs.size(), false);//是否被访问过
			while (1) {
				int i;
				for (i = 0; i < hash.size(); i++) {//检查遍历完了没
					if (!hash[i]) break;
				}

				if (i != hash.size())
					_DFS_Func(hash, i);
				else break;

				cout << endl;
			}
		}

		struct Edge {//用于方便构造最小生成树
			W _w;//权值
			int _src;//该边出发的顶点的值
			int _dst;//该边指向的顶点的值

			Edge(W w)
				:_dst(-1),
				_src(-1),
				_w(w)
			{}
			bool operator>(const Edge& b) const
			{//用于堆中的比较
				return _w > b._w;
			}
		};


		W Kruskal(Self& mintree) {//返回权值总和，mintree用于存储最小生成树
			if (Direction) {
				cout << "该图为有向图" << endl;
				return W();
			}
			mintree._vertexs = _vertexs;//顶点都一样，边后面加
						//由于没有调用构造函数，邻接矩阵要手动初始化
			mintree._matrix.resize(_vertexs.size(), vector<W>(_vertexs.size(), MAX_W));
			priority_queue<Edge, vector<Edge>, greater<Edge> > edgeque;//小根堆存储所有边
			for (int i = 0; i < _matrix.size(); i++) {
				for (int j = 0; j < i; j++) {
					if (_matrix[i][j] != MAX_W){
						Edge temp(_matrix[i][j]);
						temp._src = i;
						temp._dst = j;
						edgeque.push(temp);
					}
				}
			}
			Unionfindset ufs(_vertexs.size());//并查集
			int count = 1;//用于判断是不是生成树
			W sum=W();//计算权值之和
			while (count!=_vertexs.size() && !edgeque.empty()) {
				Edge temp = edgeque.top();
				edgeque.pop();
				if (ufs.Findroot(temp._src) != ufs.Findroot(temp._dst)) {//用并查集判断是否构成环
					ufs.Union(temp._src, temp._dst);
					mintree._AddEdge(temp._src, temp._dst, temp._w);
					sum += temp._w;
					count++;
				}
			}
			if (count == _vertexs.size()) return sum;//判断是不是生成树
			else return W();
		}


		W Prim(Self& mintree, V src) {//st是起点
			if (Direction) {
				cout << "该图为有向图" << endl;
				return W();
			}
			mintree._vertexs = _vertexs;//顶点都一样，边后面加
						//由于没有调用构造函数，邻接矩阵要手动初始化
			mintree._matrix.resize(_vertexs.size(), vector<W>(_vertexs.size(), MAX_W));
			size_t st = _vIndexMap[src];
			vector<bool> hash(_vertexs.size(), true);//记录未连接的顶点
			hash[st] = false;
			priority_queue<Edge,vector<Edge>,greater<Edge> > edgeque;//小根堆存储附近的所有边
			for (int i = st; i < _matrix[st].size(); i++) {
				if (_matrix[st][i] != MAX_W&& i!=st) {
					Edge temp(_matrix[st][i]);
					temp._src = st;
					temp._dst = i;
					edgeque.push(temp);
				}
			}

			int count = 1;
			W sum = W();
			while (count != _vertexs.size() && !edgeque.empty()) {
				Edge temp = edgeque.top();
				edgeque.pop();
				if (hash[temp._dst]) {
					hash[temp._dst] = false;
					mintree._AddEdge(temp._src, temp._dst, temp._w);
					count++;
					sum += temp._w;
					for (int j =0; j < _matrix[temp._dst].size(); j++) {//连接的顶点的所有边加入堆
						if (_matrix[temp._dst][j] != MAX_W && hash[j]) {//hash[j]防止连到旧顶点和同一个顶点，优化一点效率
							Edge t(_matrix[temp._dst][j]);
							t._src = temp._dst;
							t._dst = j;
							edgeque.push(t);
						}
					}
				}
			}
			if (count == _vertexs.size()) return sum;//判断是不是生成树
			else return W();
		}

		//包含从起点出发到所有顶点的最短路径的信息
		void Dijkstra(V srci, vector<W>& path, vector<int>& parent) {
			size_t N = _vertexs.size();
			int sr = _vIndexMap[srci];
			path.resize(N, MAX_W);//到各个顶点的最短路径的长度
			parent.resize(N, -1);//各个顶点的在各自最短路径中的上一个节点，下面简称父节点，不断回溯即可确定其最短路径，值为-1表示父节点是自己
			vector<bool> hash(N, false);//true表示该顶点属于找到最短路径的S，反之则属于未处理的Q
			priority_queue<Edge, vector<Edge>, greater<Edge> > edgeque;//小根堆存储附近的所有边
			path[sr] = W();
			Edge t(0);
			t._dst = sr;
			t._src = sr;
			edgeque.push(t);
			while (!edgeque.empty()) {
				int cur = edgeque.top()._dst;//取的是顶点而不是边
				//判断一下从这条边到达是不是最短路径，是的话要更新路径长度和父节点
				if (path[edgeque.top()._src] + edgeque.top()._w <= path[edgeque.top()._dst]) {
					path[edgeque.top()._dst] = path[edgeque.top()._src] + edgeque.top()._w;
					parent[edgeque.top()._dst] = edgeque.top()._src;
				}
				edgeque.pop();
				if (hash[cur]) continue;
				hash[cur] = true;
				for (int j = 0; j < N; j++) {
					if (hash[j] || _matrix[cur][j] == MAX_W) continue;
					Edge temp(_matrix[cur][j]);
					temp._src = cur;
					temp._dst = j;
					edgeque.push(temp);
					if (path[cur] + _matrix[cur][j] < path[j]) {//松弛，父节点会在取出边时更新
						path[j] = path[cur] + _matrix[cur][j];
					}
				}
			}
		}

		bool BellmanFord(V srci, vector<W>& path, vector<int>& parent) {
			size_t N = _vertexs.size();
			int sr = _vIndexMap[srci];
			path.resize(N, MAX_W);//到各个顶点的最短路径的长度
			parent.resize(N, -1);//各个顶点的在各自最短路径中的上一个节点，下面简称父节点，不断回溯即可确定其最短路径，值为-1表示父节点是自己
			vector<int> count(N, 0);//记录每个顶点遍历次数，防止负权环带来的死循环
			queue<int> verque;//顶点队列
			vector<bool>hash(N, false);//记录顶点是否在队列里，防重复

			path[sr] = 0;
			verque.push(sr);
			hash[sr] = true;
			while (!verque.empty()) {
				int temp = verque.front();
				verque.pop();
				hash[temp] = false;
				count[temp]++;
				if (count[temp] == N) return false;
				for (int j = 0; j < N; j++) {
					if (_matrix[temp][j]!=MAX_W && path[j] > _matrix[temp][j] + path[temp]) {
						path[j] = _matrix[temp][j] + path[temp];
						parent[j] = temp;
						if (!hash[j]) {
							verque.push(j);;
							hash[j] = true;
						}
					}
				}
			}
			return true;
		}

		void FloydWarShall(vector<vector<W>>& path, vector<vector<int>>& parent) {//path就是D
			size_t N = _vertexs.size();
			path = _matrix;//初始时就是邻接矩阵
			parent.resize(N, vector<int>(N, -1));
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (_matrix[i][j] != MAX_W && i != j) parent[i][j] = i;//父节点也要初始化
				}
			}

			for (int k = 0; k < N; k++) {
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						if (path[i][k] != MAX_W && path[k][j] != MAX_W && i != j && path[i][j] > path[i][k] + path[k][j]) {//有经过顶点k
							path[i][j] = path[i][k] + path[k][j];
							parent[i][j] = parent[k][j];
						}
					}
				}
			}
		}

		void Print() {//输出图的内容
			for (auto i : _vertexs) {//打印顶点与下标关系
				cout << i << ' ';
			}
			cout << endl;
			for (int i = 0; i < _vertexs.size(); i++) cout << i << ' ';
			cout << endl << endl;

			for (auto i : _matrix) {//打印邻接矩阵
				for (auto j : i) {
					if (j != MAX_W)
						cout << j << ' ';
					else cout << "# ";
				}
				cout << endl;
			}
			cout << endl;
			int sup;
			for (int i = 0; i < _matrix.size(); i++) {//打印所有的边
				if (Direction) sup = _matrix[i].size();
				else sup = i;

				for (int j = 0; j < sup; j++) {
					if (_matrix[i][j] != MAX_W && Direction) cout << _vertexs[i] << " --" << _matrix[i][j] << "--> " << _vertexs[j] << endl;
					else if (_matrix[i][j] != MAX_W) cout << _vertexs[i] << " --" << _matrix[i][j] << "-- " << _vertexs[j] << endl;
				}
			}
		}

		void PrinrtShotPath(V srci, vector<W>& dist, vector<int>& parent) {//打印以srci为起点的所有最短路径
			int sr = _vIndexMap[srci];
			for (int i = 0; i < parent.size(); i++)
			{
				if (i == sr) continue;
				vector<int> path;
				int cur = i;
				while (cur != -1) {
					path.push_back(cur);
					cur = parent[cur];
				}
				cout << "最短路径:" << endl;
				for (int i = path.size() - 1; i >= 0; i--) {
					cout << _vertexs[path[i]] << "->";
				}
				cout << endl;
				cout << "长度：" << dist[i] << endl << endl;
			}
		}

	private:
		vector<V> _vertexs;//顶点
		map<V, int> _vIndexMap;//映射：顶点->编号
		vector<vector<W> > _matrix;//邻接矩阵
	};
}